package com.lzy.arithmetic.tree;

import java.util.LinkedList;

public class 数组转二叉树 {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        TreeNode node = genTwoTree(nums, 0, nums.length - 1);
        // middleStepTree(node);
        levelStepTree(node);
    }

    /**
     * 递归生成二叉树
     *
     * @param nums
     * @param left
     * @param right
     * @return
     */
    public static TreeNode genTwoTree(int[] nums, int left, int right) {
        TreeNode root = new TreeNode();

        if (left <= right) {
            int mid = (left + right + 1) / 2;
            root.data = nums[mid];
            root.lChild = genTwoTree(nums, left, mid - 1);
            root.rChild = genTwoTree(nums, mid + 1, right);
        } else {
            return null;
        }
        return root;
    }

    /**
     * 二叉树中序遍历
     *
     * @param node
     */
    public static void middleStepTree(TreeNode node) {
        if (node == null) {
            return;
        }
        middleStepTree(node.lChild);
        System.out.println(node.data);
        middleStepTree(node.rChild);
    }

    /**
     * 层遍历
     * @param node
     */
    public static void levelStepTree(TreeNode node) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            TreeNode tmpNode = queue.pop();
            System.out.println(tmpNode.data);
            if (tmpNode.lChild != null) {
                queue.add(tmpNode.lChild);
            }
            if (tmpNode.rChild != null) {
                queue.add(tmpNode.rChild);
            }
        }
    }
}
